package com.lzq.leetcode.hoot100;

import java.util.ArrayList;
import java.util.List;

public class s22 {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        dfs(n, 0, new StringBuilder(), 0, 0, ans);
        return ans;
    }

    private void dfs(int n, int cur, StringBuilder temp, int stack, int l, List<String> ans) {
        // 判断结束
        if (cur > n * 2) {
            ans.add(temp.toString());
            return;
        }
        // 添加左括号
        if (l < n) {
            temp.append('(');
            dfs(n, cur+1, temp, stack+1, l+1, ans);
            temp.deleteCharAt(temp.length() - 1);
        }
        // 添加右括号
        if (stack > 0) {
            temp.append(')');
            dfs(n, cur+1, temp, stack-1, l, ans);
            temp.deleteCharAt(temp.length() - 1);
        }

    }

    public static void main(String[] args) {
        s22 s22 = new s22();
        List<String> strings = s22.generateParenthesis(3);
    }
}
